//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 由英文字母、数字、符号和空格组成 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 9860 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-12-20 23:59:26
 * @description 3.无重复字符的最长子串
 */
public class LongestSubstringWithoutRepeatingCharacters{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLongestSubstring1(String s) {
		//滑动窗口，记录每个字符最后一次出现的坐标
		//每次重复时，作为统计区间的左端点，每次记录出现的位置
		int [] last= new int[128];
		int res=0;
		int l=0;
		for (int i = 0; i < s.length(); i++) {
			//ascii码
			int index=s.charAt(i);
			//更新左端点
			l=Math.max(l,last[index]);
			//更新结果
			res=Math.max(res,i-l+1);
			//保存结果
			last[index]=i+1;
		}
		return res;
    }


	//滑动窗口,hash实现
	public int lengthOfLongestSubstring(String s) {
		Map<Character,Integer> map=new HashMap<>();
		int l=0,res=0;
		for (int i = 0; i < s.length(); i++) {
			if(map.containsKey(s.charAt(i))){
				l=Math.max(l,map.get(s.charAt(i))+1);
			}
			map.put(s.charAt(i),i);
			res=Math.max(res,i-l+1);
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
